In image processing, a neighborhood process is one in which each image pixel is visited in a specified order. For a pixel visited, each neighbor pixel within a defined neighborhood is also visited. For example, a neighborhood of pixel p might be defined as the set of pixels immediately above, below, to the left, and to the right of p. Neighborhood processes may be used in many image processing operations, such as, e.g., convolution, median filtering, erosion, dilation, etc.
FIG. 1 illustrates an exemplary two-dimensional lattice structure 100, where each lattice node, e.g. node 102, is a pixel. If a ‘neighbor’ is defined as one of the four nodes that is immediately above, below, left or right of a given node, then the nodes in the gray area 104 are nodes having neighbors that are all within the lattice boundaries. Nodes having a full set of neighbors, in this example, four neighbors, are known as interior nodes. The nodes in the white area 106 each are missing at least one neighbor within the boundaries of the lattice. The nodes in border area 106 are known as boundary nodes.
FIG. 2 illustrates another exemplary two-dimensional lattice structure, where a neighbor is defined as one of the eight nodes that is immediately adjacent to a given node. Node 202 is an interior node with a full set 204 of eight neighbors. Node 206 is a boundary node with only five neighbors.
A variation of the neighborhood process is one in which pixels are processed from a queue (e.g., a first-in first-out data structure). At each step of the process, the next pixel is obtained from the queue and each of its neighbors is visited. Neighboring pixels that satisfy certain criteria are added to the queue. The process continues until the queue is empty. Queue-based neighborhood processes include, for example, the watershed transform, regional minima detection, etc.
An important consideration when implementing a neighborhood process is how to handle image boundaries. For example, if the current pixel being visited is on the top row, then there is no neighbor “above” that pixel, and any attempt to access such a non-existent pixel will cause the software to fail.
Conventional programming techniques for handling bounds checking in neighborhood processes include checking to make sure a neighbor pixel is in bounds before every attempt to visit the neighbor pixel. This technique is computationally expensive because it inserts multiple conditional branches within the inner-most loop of the software. Another technique is to pad the image boundaries so that all of the original image pixels have neighbors that are in-bounds in the padded image. This technique often runs faster because the conditional branches are eliminated, but it requires more memory in the form of an extra copy of the image. Yet another technique is to divide the image into sections, processing each section with different code. Sections near the image boundaries are processed using code that does explicit bounds-checking, whereas sections in the image interior are processed using code that does not do bounds-checking. This technique may have acceptable speed and/or memory characteristics. However, dividing an image into sections may complicate the software considerably, making programming errors more likely. Dividing and image also does not extend easily to higher dimensions, nor can it handle queue-based neighborhood processes.